#include<stdio.h>
#include<iostream>
using namespace std;
#define Status int
#define OK true
//图的遍历  
//遍历的实质：找每个顶点的邻接点的过程 
//避免重复访问：设置辅助数组visited[n], 用来标记每个被访问过的顶点
//				初始状态visited[i]为0;	顶点i被访问，改visited[i]为1，防止被多次访问 

//图常用的遍历
//1. 深度优先搜索(Depth_First Search ---- DFS)
//2. 广度优先搜索(Breadth_First Search ---- BFS) 



//邻接矩阵表示的无向图深度遍历算法的实现：
#define MaxInt 32767
#define MVNum 100
typedef char VertexType; 
typedef int ArcType;
typedef struct {
	VertexType vexs[MVNum];
	ArcType arcs[MVNum][MVNum];
	int vexnum, arcnum;
}AMGraph;
//算法：在图中查找顶点
int LocateVex(AMGraph G, VertexType u){
	//图G中查找顶点u，存在则返回顶点表中的下标; 否则返回 -1
	for(int i = 0; i < G.vexnum; ++i){
		if(u == G.vexs[i]) return i;
	} 
	return -1;
}
//算法6.1 采用邻接矩阵表示法创建无向网  
Status CreateUDN(AMGraph &G){
	cin>>G.vexnum>>G.arcnum; //输入总顶点数，总边数  
	
	for(int i = 0; i < G.vexnum; ++i){
		cin>>G.vexs[i];  //依次输入点的信息 
	}
	
	for(int i = 0; i < G.vexnum; ++i){  //初始化邻接矩阵 
		for(int j = 0; j < G.vexnum; ++j){
			G.arcs[i][j] = MaxInt;  //边的权值均置为极大值 
		}
	}
	
	for(int k = 0; k < G.arcnum; ++k) {  //构造邻接矩阵  
		VertexType v1, v2;
		ArcType w;
		cin>>v1>>v2>>w; //输入一条边所依附的顶点及权值
		int i = LocateVex(G, v1);
		int j = LocateVex(G, v2); //确定v1, v2在G中的位置
		
		G.arcs[i][j] = w; //边<v1, v2>在G中的位置 
		G.arcs[j][i] = G.arcs[i][j]; //置<v1, v2>的对称边 <v2, v1>的权值为w 
	}
	
	return OK;
}//CreateUDN

//算法6.5 采用邻接矩阵表示图的深度优先搜索遍历 
void DFS(AMGraph G, int v) { //图G为邻接矩阵类型 
	cout<<v;
	visited[v] = true; //访问第v个顶点
	for(int w = 0; w < G.vexnum; v++){ //依次检查邻接矩阵v所在的行 
		if((G.arcs[v][w] != 0) && (!visited[w]))
			DFS(G, w);
		//w是v的邻接点，如果w未访问，则递归调用DFS 
	} 
	
} 

 
 


//算法6.7 按广度优先遍历非递归遍历连通图 
void BFS(AMGraph G, int v){ 
	cout<<v;
	visited[v] = true; //访问第v个顶点 
	InitQueue(Q);  //辅助队列初始化，置空 
	EnQueue(Q, v); //v进队 
	while(!QueueEmpty(Q)){ //队列非空 
		DeQueue(Q, u);  //队头元素出队并置为w 
		for(int w = FirstAdjvex(G, u); w > 0; w = NextAdjVex(G, u, w))
		if(!visited[w]){ //w为u的尚未访问的邻接顶点 
			cout<<w;
			visited[w] = true;
			EnQueue(Q, w); //w出队 
		}//if
	}//while
} 


int main(void)
{
	
	
	return 0;
} 